/**
 * @Author: zxc
 * @Date: 2020-11-03 13:47:40
 * @func:最长回文子串
 */

/**
 * @param {string} s
 * @return {string}
 */
// var longestPalindrome = function(s) {
//   if( !s || s.length < 2 ) return s
//   let res = '' , i = s.length -  1
//   const dp = []
//   for( res = s[i] ; i >= 0 ; i--){
//       dp[i] = [];
//       let j = i
//       for( ; j < s.length ; j++){
//           if(j === i) dp[i][j] = true
//           else if(j - i === 1 && s[i] === s[j]) dp[i][j] = true;
//           else if(s[i] === s[j] && dp[i+1][j-1]) dp[i][j] = true;
//           if(dp[i][j] && j-i+1 > res.length){
//               res = s.substring( i , j+1 )
//           }
//       }
//   }
//   return res
// };

// const centerExtend = (left, right, len, s) => {
//   while (left >= 0 && right < len && s[left] === s[right]) {
//     left--;
//     right++;
//   }
//   return {
//     len: right - left - 1,
//     left: left + 1,
//     right: right - 1,
//   };
// };

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  if (!s || s.length < 2) return s
  let i = 0,
    start = 0,
    end = 0,
    maxLength,
    left,
    right
  const len = s.length
  for (; i < len; i++) {
    let { len: len1, left: left1, right: right1 } = centerExtend(i, i, len, s)
    let { len: len2, left: left2, right: right2 } = centerExtend(
      i,
      i + 1,
      len,
      s
    )
    if (len1 > len2) {
      maxLength = len1
      left = left1
      right = right1
    } else {
      maxLength = len2
      left = left2
      right = right2
    }
    if (maxLength > end - start) {
      start = left
      end = right
    }
  }

  return s.substring(start, end + 1)
}
